package com.example.leetcode.tree;

import java.util.Arrays;

/**
 * 将有序数组转换为二叉搜索树
 *
 * 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。
 * 输入：nums = [-10,-3,0,5,9]
 * 输出：[0,-3,9,-10,null,5]
 * 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案
 *
 *
 */
public class SortedArrayToBST {






    public TreeNode sortedArrayToBST2(int[] nums) {
        //每次将中点作为根节点，其左边的所有元素作为左子树，右边的所有元素作为右子树
        if (nums.length == 0) {
            return null;
        }
        int mid = nums.length / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = sortedArrayToBST(Arrays.copyOfRange(nums, 0, mid));
        root.right = sortedArrayToBST(Arrays.copyOfRange(nums, mid+1, nums.length-1));

        return root;
    }



























    public TreeNode sortedArrayToBST(int[] nums) {
        //每次将中点作为根节点，其左边的所有元素作为左子树，右边的所有元素作为右子树
        if(nums.length == 0){
            return null;
        }
        int mid = nums.length/2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = sortedArrayToBST(Arrays.copyOfRange(nums,0,mid));
        root.right = sortedArrayToBST(Arrays.copyOfRange(nums,mid+1,nums.length));
        return root;
    }
}
